package training;

import java.util.ArrayList;
import java.util.List;
import java.util.TreeMap;

/**
 * @Author liangzai
 * @Description:
 */
public class J25_7_10_Training {
    //重新安排会议得到最多空余时间 II
    public int maxFreeTime(int eventTime, int[] startTime, int[] endTime) {
        // 先统计出空隙
        TreeMap<Integer, Integer> buffersMap = new TreeMap<>();
        List<Integer> buffers = new ArrayList<>();
        buffers.add(startTime[0]);
        buffersMap.put(startTime[0], 1);
        for (int i = 0; i < startTime.length - 1; i++) {
            int buffer = startTime[i + 1] - endTime[i];
            buffers.add(buffer);
            buffersMap.put(buffer, buffersMap.getOrDefault(buffer, 0) + 1);
        }
        int lastBuffer = eventTime - endTime[endTime.length - 1];
        buffers.add(lastBuffer);
        buffersMap.put(lastBuffer, buffersMap.getOrDefault(lastBuffer, 0) + 1);
        // 计算相邻空隙的最大值
        int max = 0;
        for (int i = 1; i < buffers.size(); i++) {
            int buffer1 = buffers.get(i - 1);
            int buffer2 = buffers.get(i);
            int meeting = endTime[i - 1] - startTime[i - 1];
            int sum = buffer1 + buffer2;
            // 看看是否有其它更大的空隙可以塞入meeting
            buffersMap.put(buffer1, buffersMap.get(buffer1) - 1);
            if (buffersMap.get(buffer1) == 0) {
                buffersMap.remove(buffer1);
            }
            buffersMap.put(buffer2, buffersMap.get(buffer2) - 1);
            if (buffersMap.get(buffer2) == 0) {
                buffersMap.remove(buffer2);
            }
            if (buffersMap.containsKey(meeting) || buffersMap.higherKey(meeting) != null) {
                sum += meeting;
            }
            max = Math.max(max, sum);
            // 恢复空隙
            buffersMap.put(buffer1, buffersMap.getOrDefault(buffer1, 0) + 1);
            buffersMap.put(buffer2, buffersMap.getOrDefault(buffer2, 0) + 1);
        }
        return max;
    }
}
